package 动态规划.backageQuestion;

/**
 * 0 -1 背包问题
 *  解题分析：
 *  0-1 背包问题是动态规划中的经典问题。在这个问题中，你有一个背包和一些物品。
 * 每个物品有其重量和价值，背包有一个最大承重。你的任务是确定应该将哪些物品放入背包，以使得背包中的物品总价值最大，同时不超过背包的最大承重。
 *  核心要素
 * 物品：每个物品有两个属性，重量（weight）和价值（value）。
 * 背包容量：背包有最大承重限制（capacity）。
 * 最优子结构：
 *  对于每个物品，你有两个选择：放入背包或不放入背包。如果放入背包，背包的剩余容量减少，但总价值增加；如果不放入背包，则背包的剩余容量和总价值都不变。
 * 重叠子问题：
 *  在考虑每个物品是否放入背包时，你会多次考虑相同的子问题，例如，考虑剩余容量为 x 时的最大价值。
 *
 *  状态转移方程
 * 定义 dp[i][w] 为考虑前 i 个物品，当背包容量为 w 时的最大价值。状态转移方程如下：
 *
 * 如果不选择第 i 个物品：dp[i][w] = dp[i-1][w]
 * 如果选择第 i 个物品：dp[i][w] = dp[i-1][w-weight[i]] + value[i]   // 放入第i个物品之前的最大值，然后加上第i个物品的价值
 *
 *  选择与不选择第 i 个物品的判断条件为：如果选择了第i个物品，背包容量必须大于第i个物品的重量。
 *
 * 整体方程：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
 *
 * 背包问题的
 * @Author lf
 * @Date 3/18/2024
 */
public class ZeroToOneBackage {

    /**
     *
     * @param values 物品的价值
     * @param weights 物品的重量
     * @param capacity 背包的最大容量 （重量）
     * @return
     */
    public static int knapsack(int[] values, int[] weights, int capacity){
        // 物品的价值数组下标也是物品的数量
        int n = values.length;
        // 定义dp二维数组，表示当前背包的物品数量和当前容量的最大价值
        int[][] dp =new int[n+1][capacity+1];
        // 因为推导公式是从1开始的，所以循环从1开始
        for (int i = 1; i <= n ; i++) {
            for(int w= 1; w<= capacity; w++){
                // 如果物品的重量小于等于当前背包的容量，就选择加入
                // 数组下标从0开始的，所以实际数组i-1开始
                if(weights[i-1] <= w){
                    // 注意这里，概念不一样，dp[i] = dp[i-1]，整体方程：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])，
                    // 但是实际数组下标从0开始的，所以weights[i-1] 与 value[i-1]是当前物品的重量与价值
                    dp[i][w] = Math.max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1]);
                }else {
                    dp[i][w] = dp[i-1][w];
                }
            }
        }
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120};  // 物品的价值
        int[] weights = {10, 20, 30};   // 物品的重量
        int capacity = 50;              // 背包的容量

        System.out.println("Maximum value we can obtain = " + knapsack(values, weights, capacity));

    }
}
